{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All The Lonely Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getLonelyNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找所有的独生节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二叉树中，如果一个节点是其父节点的唯一子节点，则称这样的节点为 &ldquo;<strong>独生节点</strong>&rdquo; 。二叉树的根节点不会是独生节点，因为它没有父节点。</p>\n",
    "\n",
    "<p>给定一棵二叉树的根节点&nbsp;<code>root</code> ，返回树中<strong> 所有的独生节点的值所构成的数组</strong> 。数组的顺序<strong> 不限 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/03/e1.png\" style=\"height:202px; width:203px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,4]\n",
    "<strong>输出：</strong>[4]\n",
    "<strong>解释：</strong>浅蓝色的节点是唯一的独生节点。\n",
    "节点 1 是根节点，不是独生的。\n",
    "节点 2 和 3 有共同的父节点，所以它们都不是独生的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/03/e2.png\" style=\"height:282px; width:442px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [7,1,4,6,null,5,3,null,null,null,null,null,2]\n",
    "<strong>输出：</strong>[6,2]\n",
    "<strong>输出：</strong>浅蓝色的节点是独生节点。\n",
    "请谨记，顺序是不限的。 [2,6] 也是一种可接受的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/03/tree.png\" style=\"height:202px; width:363px\" /> </strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]\n",
    "<strong>输出：</strong>[77,55,33,66,44,22]\n",
    "<strong>解释：</strong>节点 99 和 88 有共同的父节点，节点 11 是根节点。\n",
    "其他所有节点都是独生节点。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [197]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [31,null,78,null,28]\n",
    "<strong>输出：</strong>[78,28]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>&nbsp;<code>tree</code>&nbsp;中节点个数的取值范围是&nbsp;<code>[1, 1000]</code>。</li>\n",
    "\t<li>每个节点的值的取值范围是&nbsp;<code>[1, 10^6]</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-the-lonely-nodes](https://leetcode.cn/problems/find-all-the-lonely-nodes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-the-lonely-nodes](https://leetcode.cn/problems/find-all-the-lonely-nodes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,4]', '[7,1,4,6,null,5,3,null,null,null,null,null,2]', '[11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        q = [root]\n",
    "        ans = []\n",
    "        while q:\n",
    "            nq = []\n",
    "            for x in q:\n",
    "                if x.left and not x.right:\n",
    "                    ans.append(x.left.val)\n",
    "                if not x.left and x.right:\n",
    "                    ans.append(x.right.val)\n",
    "                if x.left: nq.append(x.left)\n",
    "                if x.right: nq.append(x.right)\n",
    "            q = nq\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        d = defaultdict(list) # parent:children\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.left:\n",
    "                d[node].append(node.left.val)\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                d[node].append(node.right.val)\n",
    "                q.append(node.right)\n",
    "        res = []\n",
    "        for k in d:\n",
    "            if len(d[k]) == 1:\n",
    "                res.append(d[k][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        q=deque([root])\n",
    "        res=[]\n",
    "        if not root :\n",
    "            return res\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node=q.popleft()\n",
    "                if node.left   :\n",
    "                    if not node.right:\n",
    "                        res.append(node.left.val)\n",
    "                    q.append(node.left)\n",
    "                if node.right :\n",
    "                    if not node.left:\n",
    "                        res.append(node.right.val)\n",
    "                    q.append(node.right)\n",
    "        return res\n",
    "                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left and not node.right:\n",
    "                    res.append(node.left.val)\n",
    "                if node.right and not node.left:\n",
    "                    res.append(node.right.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "\n",
    "            if root.left == None and root.right != None:\n",
    "                res.append(root.right.val)\n",
    "            elif root.right == None and root.left != None:\n",
    "                res.append(root.left.val)\n",
    "\n",
    "        res = []\n",
    "        traverse(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "       #liu\n",
    "       res=[]\n",
    "\n",
    "       def preorder(node):\n",
    "           if node is None: return\n",
    "\n",
    "           if (not node.left) and node.right:\n",
    "               res.append(node.right.val)\n",
    "                \n",
    "           if (not node.right) and node.left:\n",
    "               res.append(node.left.val)\n",
    "\n",
    "           preorder(node.left)\n",
    "           preorder(node.right)\n",
    "\n",
    "       preorder(root)\n",
    "\n",
    "       return res\n",
    "               \n",
    "\n",
    "       # 这种写法是比较典型的先序/中序/后序遍历。创建数组-创建函数-调用函数-返回数组\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res  = []\n",
    "\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.left==None and root.right!=None:\n",
    "            self.res.append(root.right.val)\n",
    "        if root.right==None and root.left!=None:\n",
    "            self.res.append(root.left.val)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        \n",
    "        output = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.left and node.right:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "                else:\n",
    "                    if node.left:\n",
    "                        output.append(node.left.val)\n",
    "                        dfs(node.left)\n",
    "                    elif node.right:\n",
    "                        output.append(node.right.val)\n",
    "                        dfs(node.right)\n",
    "        dfs(root)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left and not node.right:\n",
    "                ans.append(node.left.val)\n",
    "            if not node.left and node.right:\n",
    "                ans.append(node.right.val)\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return\n",
    "\n",
    "        ans = []\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left and not root.right:\n",
    "                res.append(root.left.val)\n",
    "            if not root.left and root.right:\n",
    "                res.append(root.right.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.arr = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.left or node.right:\n",
    "                if node.left is None:\n",
    "                    self.arr.append(node.right.val)\n",
    "                elif node.right is None:\n",
    "                    self.arr.append(node.left.val)\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            pass\n",
    "\n",
    "        dfs(root)\n",
    "        return self.arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: TreeNode) -> List[int]:\n",
    "        self.res = []\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    # 二叉树遍历函数\n",
    "    def traverse(self, root: TreeNode) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        # 发现独生节点\n",
    "        if not root.left and root.right:\n",
    "            self.res.append(root.right.val)\n",
    "        if root.left and not root.right:\n",
    "            self.res.append(root.left.val)\n",
    "        \n",
    "        # 二叉树遍历框架\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        if root.left and root.right is None:\n",
    "            res.append(root.left.val)\n",
    "\n",
    "        elif root.left is None and root.right:\n",
    "            res.append(root.right.val)\n",
    "\n",
    "        res.extend(self.getLonelyNodes(root.left))\n",
    "        res.extend(self.getLonelyNodes(root.right))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.ans=[]\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left=dfs(root.left)\n",
    "            root.right=dfs(root.right)\n",
    "            if root.left and not root.right:\n",
    "                self.ans.append(root.left.val)\n",
    "            elif root.right and not root.left:\n",
    "                self.ans.append(root.right.val)\n",
    "            return root\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    def traverse(self,root):\n",
    "        if(root==None):\n",
    "            return\n",
    "        if(root.left==None and root.right!=None):\n",
    "            self.res.append(root.right.val)\n",
    "        if(root.right==None and root.left!=None):\n",
    "            self.res.append(root.left.val)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "\n",
    "        def dfs(root, res):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.left and root.right is None:\n",
    "                res.append(root.left.val)\n",
    "            elif root.right and root.left is None:\n",
    "                res.append(root.right.val)\n",
    "            \n",
    "            dfs(root.left, res)\n",
    "            dfs(root.right, res)\n",
    "        \n",
    "        res = []\n",
    "        dfs(root, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.res = []\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        if not root.left and root.right:\n",
    "            self.res.append(root.right.val)\n",
    "        if not root.right and root.left:\n",
    "            self.res.append(root.left.val)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans=[]\n",
    "        def dfs(node,parent):\n",
    "            if node:\n",
    "                if parent!=None and ((node==parent.left and parent.right==None) or (node==parent.right and parent.left==None)):\n",
    "                    ans.append(node.val)\n",
    "                dfs(node.left,node)\n",
    "                dfs(node.right,node)\n",
    "        dfs(root,None)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.res = []\n",
    "\n",
    "        self.traverse(root)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if root.left and root.right is None:\n",
    "            self.res.append(root.left.val)\n",
    "        elif root.right and root.left is None:\n",
    "            self.res.append(root.right.val)\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.res = []\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.left and not root.right:\n",
    "                    self.res.append(root.left.val)\n",
    "                    dfs(root.left)\n",
    "                elif root.right and not root.left:\n",
    "                    self.res.append(root.right.val)\n",
    "                    dfs(root.right)\n",
    "                elif root.left and root.right:\n",
    "                    dfs(root.left)\n",
    "                    dfs(root.right)\n",
    "                else:\n",
    "                    return\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# ### my:后序遍历\n",
    "# class Solution:\n",
    "#     def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "#         self.ans=[]\n",
    "#         def dfs(root):\n",
    "#             if not root:\n",
    "#                 return None\n",
    "#             root.left=dfs(root.left)\n",
    "#             root.right=dfs(root.right)\n",
    "#             if root.left and not root.right:\n",
    "#                 self.ans.append(root.left.val)\n",
    "#             elif root.right and not root.left:\n",
    "#                 self.ans.append(root.right.val)\n",
    "#             return root\n",
    "#         dfs(root)\n",
    "#         return self.ans\n",
    "\n",
    "### 网：中序遍历\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def DFS(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            else:\n",
    "                DFS(root.left)\n",
    "                if not root.right and root.left:\n",
    "                    ans.append(root.left.val)\n",
    "                elif not root.left and root.right:\n",
    "                    ans.append(root.right.val)\n",
    "                DFS(root.right)\n",
    "        ans = []\n",
    "        DFS(root)\n",
    "        return ans\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/find-all-the-lonely-nodes/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root.left != None and root.right != None:\n",
    "            return self.getLonelyNodes(root.left) + self.getLonelyNodes(root.right)\n",
    "        elif root.left != None:\n",
    "            return [root.left.val] + self.getLonelyNodes(root.left)\n",
    "        elif root.right != None:\n",
    "            return [root.right.val] + self.getLonelyNodes(root.right)\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        if root.left is None and root.right:\n",
    "            res.append(root.right.val)\n",
    "        elif root.right is None and root.left:\n",
    "            res.append(root.left.val)\n",
    "\n",
    "        res.extend(self.getLonelyNodes(root.left))\n",
    "        res.extend(self.getLonelyNodes(root.right))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.output = []\n",
    "        \n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.left and not node.right:\n",
    "                    self.output.append(node.left.val)\n",
    "                    dfs(node.left)\n",
    "                elif node.right and not node.left:\n",
    "                    self.output.append(node.right.val)\n",
    "                    dfs(node.right)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.output\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans=[]\n",
    "        def dfs(node,parent):\n",
    "            if node:\n",
    "                if parent!=None and ((node==parent.left and parent.right==None) or (node==parent.right and parent.left==None)):\n",
    "                    ans.append(node.val)\n",
    "                dfs(node.left,node)\n",
    "                dfs(node.right,node)\n",
    "        dfs(root,None)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        l = []\n",
    "        def check(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and root.right:\n",
    "                l.append(root.right.val)\n",
    "            if root.left and not root.right:\n",
    "                l.append(root.left.val)\n",
    "            check(root.left)\n",
    "            check(root.right)\n",
    "        check(root)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.left and not root.right:\n",
    "            self.res.append(root.left.val)\n",
    "        if root.right and not root.left:\n",
    "            self.res.append(root.right.val)\n",
    "        self.dfs(root.left)\n",
    "        self.dfs(root.right)\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.res: List = []\n",
    "        self.dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ret=[]\n",
    "        def getans(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left and root.right:\n",
    "                getans(root.left)\n",
    "                getans(root.right)\n",
    "            elif root.left and not root.right:\n",
    "                getans(root.left)\n",
    "                ret.append(root.left.val)\n",
    "            elif root.right and not root.left:\n",
    "                getans(root.right)\n",
    "                ret.append(root.right.val)\n",
    "        getans(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left and not node.right:\n",
    "                ans.append(node.left.val)\n",
    "            if not node.left and node.right:\n",
    "                ans.append(node.right.val)\n",
    "\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "            return\n",
    "\n",
    "        ans = []\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        arr = []\n",
    "        if not root: return arr\n",
    "        def dfs(root):\n",
    "            if not root: return None\n",
    "            if root.left and not root.right:\n",
    "                arr.append(root.left.val)\n",
    "            if root.right and not root.left:\n",
    "                arr.append(root.right.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return arr                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def DFS(root):\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if root.left and not root.right:\n",
    "                ans.append(root.left.val)\n",
    "            if root.right and not root.left:\n",
    "                ans.append(root.right.val)\n",
    "            DFS(root.left)\n",
    "            DFS(root.right)\n",
    "\n",
    "        ans = []\n",
    "        DFS(root)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
